#pragma once

#include <iostream>
#include "__hash.h"
#include "dictionary.h"
#include "sortedChain.h"

/* Hash Table using sorted chains and division 
 * Implements all dictionary methods
 */

using namespace std;

template<class K, class E> 
class hashChains : public dictionary<K, E> {

    public:
        explicit hashChains(const int theDivisor = 11) {
            divisor = theDivisor;
            dSize = 0;

            table = new sortedChain<K,E>[divisor];
        } 

        ~hashChains() override { delete [] table; }

        bool empty() const override { return dSize == 0; }
        int size() const override { return dSize; }

        pair<const K, E>* find(const K& theKey) const override{
            return table[hash(theKey) % divisor].find(theKey);
        }

        void insert(const pair<const K, E>& thePair) override {

            int homeBucket = static_cast<int>(hash(thePair.first)) % divisor;
            int homeSize = table[homeBucket].size();
            table[homeBucket].insert(thePair);
            if(table[homeBucket].size() > homeSize) 
                dSize++;
            
        }

        void erase(const K& theKey) override {
            table[hash(theKey) % divisor].erase(theKey);
        }

        void output(ostream& out) const {
            for(int i = 0; i < divisor; i++) 
                if(table[i].size() == 0) 
                    out << "NULL" << endl;
                else 
                    out << table[i] << endl;
        }

    protected:
        /* hash table */
        sortedChain<K, E>* table;
        /* maps type K to non-negative integer */
        __hash<K> hash;
        /* number of elements in list */ 
        int dSize;
        /* hash function divisor */
        int divisor;

};

template<class K, class E>
ostream& operator<<(ostream& out, const hashChains<K,E>& x)
{
    x.output(out);
    return out;
}

